
/**
从有序数组中找出某个数出现的次数

其实可以直接统计的。理解简单。

有序数组，也可以使用折半查找，有序数组，某个数一定是一起出现
只要找到该数出现的起点和终点，相减即可。
*/

#include <iostream>
using namespace std;

int bin_search_index(int arr[],int len,int key,int flag)// flag = 0往左查，flag=1往右查
{
    int low = 0,high = len-1;
    int mid = 0;
    int index = -1;

    while(low<=high)
    {
        mid = (low+high)/2;
        if(key <arr[mid])
        {
            high = mid-1;
        }else if(key>arr[mid])
        {
            low = mid+1;
        }else
        {
            index = mid;
            if(flag == 0)
            {
                high = mid-1;
            }
            if(flag ==1)
            {
                low = mid+1;
            }
        }
    }
    return index;
}

int getCount(int arr[],int n,int key)
{
    //折半查找，查找到后，并不返回，而是左边查，右边查，找到左边界和右边界
    int left,right;
    left = bin_search_index(arr,n,key,0);
    right = bin_search_index(arr,n,key,1);
    return right-left+1;

}
int main()
{
    int arr[] = {1,3,5,5,5,5,5,5,6,9};
    cout<<"计数："<<getCount(arr,10,5)<<endl;
    system("pause");
    return 0;
}
